Theo thần phả đã có sự sửa đổi, Lê Thị Hoa sinh ngày 15 tháng 11 năm Kỷ Mùi (2 TCN), con gái ông Lê Thái và bà Dương Thị Tạo ở thôn Thượng Linh, xã Cảo Linh, huyện Thiên Bản, phủ Nghĩa Hưng, đạo Nam Sơn (nay là thôn Thượng Linh (làng Giềng), xã Đại Thắng, huyện Vụ Bản, tỉnh Nam Định). Tương truyền lúc mới sinh ra bà có khuôn mặt trắng như trứng gà bóc và nụ cười như hoa nên được đặt tên là Lê Thị Hoa. Năm 18 tuổi bà kết hôn cùng ông Mai Tiến (19 tuổi) người cùng huyện là người văn võ toàn tài.

Bà cùng ông Mai Tiến sinh được 3 người con là Mai Đạt (sinh năm Mậu Dần 18), Mai Thỏa (sinh năm Canh Thìn 20), Mai An (sinh năm Nhâm Ngọ 22). Sau đó cả gia đình chuyển sang huyện Gia Lâm khi ông Mai Tiến ra làm quan huyện. Ở Gia Lâm bà sinh hạ thêm người con thứ tư là Mai Trí (năm Ất Dậu 25).

Năm 34 nhà Đông Hán cử Tô Định sang làm Thái thú ở Giao Chỉ. Tô Định là một viên thái thú vô cùng tàn bạo, một mặt vơ vét của cải của dân Giao Chỉ, một mặt thẳng tay đàn áp những người chống đối ách Bắc thuộc. Bấy giờ lòng căm phẫn của các tầng lớp nhân dân Giao Chỉ đối với ách thống trị tàn bạo của nhà Đông Hán ngày một dâng cao, chỉ chờ có cơ hội là giáng bão lửa xuống bè lũ xâm lược.

Mai Tiến làm quan hết sức thanh liêm, thương dân như con nên được nhân dân tôn kính, song điều đó lại trái với chính sách cai trị của phong kiến đô hộ phương Bắc. Đây là nguyên nhân khiến ông bị Thái thú Tô Định một kẻ tàn bạo và háo sắc âm mưu hãm hại, bắt giết vào năm Bính Tuất. Ngay trong đêm đó bà Lê Thị Hoa đã cùng 4 người con và những người thân tín rời khỏi huyện Gia Lâm tới thôn Thượng Linh (làng Giềng), xã Đại Thắng, huyện Vụ Bản, tỉnh Nam Định (quê ngoại của bà) với lòng quyết tâm trả thù cho chồng. Tại đây bà chiêu mộ nghĩa sĩ chống lại Tô Định, nhưng do lực lượng còn mỏng nên phải rút về phủ Trường An lấy vùng đất Yên Nội (nay thuộc huyện Nga Sơn, tỉnh Thanh Hóa) là nơi khởi nghiệp trả thù cho chồng và đánh đuổi quân xâm lược.